#ifndef __LINK_LIST_H__
#define __LINK_LIST_H__

#include "fwDefine.h"

template <class Type> class Linkedlist
{
private:
	/**
	Struct element
	*/
	typedef struct _Element
	{
		Type * Value;
		_Element * Prev;
		_Element * Next;

		_Element(Type * value)
			: Value(value), Prev(NULL), Next(NULL)
		{
		}
		~_Element()
		{
			SAFE_DEL(Value);

			if (Next)
				Next->Prev = Prev;
			if (Prev)
				Prev->Next = Next;
		}
	}Element;
private:
	_Element * m_temp;
	_Element * m_first;
	_Element * m_last;
	_Element * m_iterate;
public:
	//List size
	FWuint Count;
public:
	Linkedlist()
		: m_temp(NULL),
		m_first(NULL), m_last(NULL), m_iterate(NULL), Count(0)
	{

	}

	~Linkedlist()
	{
		Clear();
	}

	//Clear all elements in list
	void Clear()
	{
		while (m_last != NULL)
		{
			m_temp = m_last;
			m_last - m_last->Prev;
			SAFE_DEL(m_temp);
		}
		m_first = m_last = m_iterate = m_temp = NULL;
		Count = 0;
	}

	//Add new element at Last of list
	void Add(Type * value)
	{
		if (value == NULL)
			return;

		if (m_first == NULL)
		{
			m_first = new _Element(value);
			m_last = m_first;
		}
		else
		{
			m_last->Next = new _Element(value);
			m_last->Next->Prev = m_last;
			m_last = m_last->Next;
		}

		Count++;
	}

	//Insert new element before a node in list
	void InsertBefore(Type * value, _Element * next)
	{
		if (next == NULL)
			return;

		m_temp = next->Prev;
		Count++;

		if (m_temp == NULL)
		{
			m_first = new _Element(value);
			m_first->Next = next;
			next->Prev = m_first;
		}
		else
		{
			m_temp->Next = new Element(value);
			m_temp->Next->Prev = m_temp;
			m_temp->Next->Next = next;
			next->Prev = m_temp->Next;
		}
	}

	//Remove element from the list and destroy its data
	void Remove(Type** value)
	{
		m_temp = m_first;
		while (m_temp != NULL)
		{
			if (m_temp->Value == *value)
			{
				if (m_temp == m_first)
				{
					m_first = m_first->Next;
					if (m_first != NULL)
						m_first->Prev = NULL;
				}
				if (m_temp == m_last)
				{
					m_last = m_last->Prev;
					if (m_last != NULL)
						m_last->Next = NULL;
				}
				SAFE_DEL(m_temp->Value);
				*value = NULL;
				Count--;
				return;
			}
			m_temp = m_temp->Next;
		}
	}

	//Return a first value of element in the list 
	Type * First()
	{
		if (m_first == NULL)
			return NULL;
		return m_first->Value;
	}

	//Iterates through the elements in the linked list
	Type * Iterate(bool restart = false)
	{
		//Restart to start point
		if (restart)
			m_iterate = NULL;

		//Check m_iterate start point
		if (m_iterate == NULL)
			m_iterate = m_first;
		else
			m_iterate = m_iterate->Next;

		//return m_iterate value
		if (m_iterate == NULL)
			return NULL;
		else
			return m_iterate->Value;
	}

	//Return a last value of element in the list
	Type * Last()
	{
		if (m_last == NULL)
			return NULL;
		return m_last->Value;
	}

	//Return value of next element in the list from given value
	Type * NextValue(Type * value)
	{
		if (value == NULL)
			return NULL;

		m_temp == m_first;
		while (m_temp != NULL)
		{
			if (m_temp->Value == value)
			{
				if (m_temp->Next == NULL)
					return NULL;
				return m_temp->Next->Value;
			}
			m_temp = m_temp->Next;
		}
		return NULL;
	}

	//Return a random value of element in the list
	Type * RandomValue()
	{
		if (Count == 0)
			return NULL;
		if (Count == 1)
			return m_first->Value;

		FWulong index = rand() * Count / MAX_RAND; //Nghi van loi
		m_temp = m_first;
		for (FWulong i = 0; i < index; i++)
			m_temp = m_temp->Next;
		return m_temp->Value;
	}
};

#endif